//带环链表
//给你一个链表的头节点 head ，判断链表中是否有环。

#include<stdio.h>
#include<stdlib.h>


struct ListNode
{
	int val;
	struct ListNode* next;
};

void SLTNodePrintf(struct ListNode* ps)
{
	struct ListNode* cur = ps;
	while (cur)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}

//思路 追及问题 
//fast一次走两步 slow一次走一步  一定可以追上
int  hasCycle(struct ListNode* head) 
{
	struct ListNode* fast = head;
	struct ListNode* slow = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
		if (fast == slow)
			return 1;
	}
	return 0;
}



int main()
{
	struct ListNode* n1 = malloc(sizeof(struct ListNode));
	struct ListNode* n2 = malloc(sizeof(struct ListNode));
	struct ListNode* n3 = malloc(sizeof(struct ListNode));
	struct ListNode* n4 = malloc(sizeof(struct ListNode));

	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n3;
	//SLTNodePrintf(n1);

	int ret = hasCycle(n1);
	if (ret == 0)
	{
		printf("false");
	}
	else
	{
		printf("ture");

	}

	return 0;
}